package seqlist;

/**
 * 不带头单链表实现
 */

class Node {
    int data;
    Node next;

    public Node(int data, Node next) {
        this.data = data;
        this.next = next;
    }
}

public class SingleLinkedList {
    private int size;
    private Node first;
    private Node last;

    public void add(int data) {
        addLast(data);
    }

    public void add(int index,int data) {
        if (index < 0 || index > size) {
            System.out.println("索引非法!");
            return;
        }
        else if (index == size) {
            addLast(data);
        }else {
            Node node = new Node(data,null);
            // 中间位置插入,获取前驱节点
            Node prev = node(index - 1);
            node.next = prev.next;
            prev.next = node;
            size ++;
        }
    }

    /**
     * 删除第一个值为data的节点
     * @param data
     */
    public void remove(int data) {
        // 头结点就是待删除的节点
        if (first.data == data) {
            Node next = first.next;
            // help GC
            first.next = null;
            first = next;
            size --;
        }else {
            for (Node x = first;x != null;x = x.next) {
                // x为待删除节点的前驱节点
                if (x.next.data == data) {
                    Node temp = x.next;
                    x.next = x.next.next;
                    temp.next = null;
                    size --;
                    return;
                }
            }
            System.out.println("链表中没有该节点");
        }
    }

    /**
     * 删除所有值为data的节点
     * @param data
     */
    public void removeAll(int data) {
//        while (first != null && first.data == data) {
//            first = first.next;
//            size --;
//        }
//        if (first == null) {
//            return;
//        }
//        Node prev = first;
//        while (prev.next != null) {
//            if (prev.next.data == data) {
//                prev.next = prev.next.next;
//                size --;
//            }else {
//                prev = prev.next;
//            }
//        }
        // 引入虚拟头结点
        Node dummyHead = new Node(data - 1,first);
        Node temp = dummyHead;
        while (temp.next != null) {
            if (temp.next.data == data) {
                temp.next = temp.next.next;
                size --;
            }else {
                temp = temp.next;
            }
        }
        first = dummyHead.next;
    }

    /**
     * 修改索引为index的节点值
     * @param index
     * @param data
     */
    public void set(int index,int data) {
        if (index < 0 || index >= size) {
            System.out.println("索引非法");
            return;
        }
        Node node = node(index);
        node.data = data;
    }

    /**
     * 获取索引为index的节点值
     * @param index
     */
    public int get(int index) {
        if (index < 0 || index >= size) {
            System.out.println("索引非法");
            return -1;
        }
        return node(index).data;
    }

    public boolean contains(int data) {
        for(Node x = first;x != null;x = x.next) {
            if (x.data == data) {
                return true;
            }
        }
        return false;
    }

    public int size() {
        return size;
    }

    public void printList() {
        Node temp = first;
        while (temp != null) {
            System.out.print(temp.data + "、");
            temp = temp.next;
        }
        System.out.println();
    }

    public void clear() {}

    /**
     * 头插
     * @param data
     */
    public void addFirst(int data) {
        Node node = new Node(data,first);
        if (last == null) {
            last = node;
        }
        first = node;
        size ++;
    }

    /**
     * 尾插
     * @param data
     */
    public void addLast(int data) {
        Node node = new Node(data,null);
        if (first == null) {
            first = last = node;
        }
        last.next = node;
        last = node;
        size ++;
    }

    /**
     * 获取索引为index的节点
     * @param index
     * @return
     */
    private Node node(int index) {
        Node temp = first;
        for (int i = 0; i < index; i++) {
            temp = temp.next;
        }
        return temp;
    }
}
